#include <bits/stdc++.h>
using namespace std;

using llt = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using pll = pair<llt, llt>;

struct Point {
    llt x;
    llt y;
    Point(llt a, llt b):x(a),y(b){}
    llt cross(const Point & r) const {
        return x * r.y - y * r.x;
    }
    const Point operator - (const Point & r) const {
        return {x - r.x, y - r.y};
    }
};

int N, K;

vector<llt> S;
vector<llt> D[2];
vector<int> Q;
vector<vi> Fangan;

void output(int n, int k){
    if(0 == n) return;

    output(Fangan[n][k], k - 1);
    cout << n << " ";
    return;
}

int Pre, Cur;

const Point get(int p){
    return {S[p], S[p] * S[p] - D[Pre][p]};
}

void work(){
    cin >> N >> K;
    S.assign(N + 1, 0);
    for(int a,i=1;i<=N;++i){
        cin >> a;
        S[i] = S[i - 1] + a;
    }

    D[0].assign(N + 1, 0);
    D[1].assign(N + 1, 0);

    Q.assign(N + 10, 0);
    Pre = 0;
    Cur = 1;

    Fangan.assign(N + 1, vi(K + 1, 0));

    for(int k=1;k<=K;++k){
        const auto & pre = D[Pre];
        auto & d = D[Cur];
        int * bot = Q.data();
        int * top = bot;
        *bot = 0;        
        for(int i=1;i<=N;++i){
            const Point now(1, S[i]);
            while(bot < top and now.cross(get(*(bot + 1)) - get(*bot)) <= 0){
                bot += 1;
            }

            Fangan[i][k] = *bot;
            d[i] = pre[*bot] + S[*bot] * (S[i] - S[*bot]);

            while(bot < top and (get(*top) - get(*(top - 1))).cross(get(i) - get(*top)) <= 0){
                top -= 1;
            }
            *++top = i;
        }        
        swap(Pre, Cur);
    }

    cout << D[Pre][N] << "\n";
    output(Fangan[N][K], K - 1);
    cout << "\n";
    return;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1;
    // cin >> nofkase;
    while(nofkase--) work();
    return 0;
}
